import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class _560和为K的子数组 {
    public static int subarraySum(int[] nums, int k) {
        int len = nums.length;
        int count = 0;
        for (int i = 0; i < len; i++) {
            //i代表结尾
            int sum=0;
            for (int j = i; j >=0; j--) {
                sum+=nums[j];
                if(sum==k){
                    count++;
                }
            }
            
        }
        return count;
    
    }

    public static void main(String[] args) {
        int[] ints={1,1,1};
       int subarraySum = subarraySumMap(ints,2);;
       System.out.println("答案1："+subarraySum);
       System.out.println("答案2："+subarraySumMap(new int[]{1,2,3,4,5},7));
       System.out.println("答案3："+subarraySumMap(new int[]{3,4,7,2,-3,1,4,2},7));
    }

    public static int subarraySumMap(int[] nums, int k) {
        int count=0,pre=0;
        Map<Integer,Integer> map=new HashMap<>();
        map.put(0,1);
        for (int i : nums) {
            pre+=i;
            if(map.containsKey(pre-k)){
                count+=map.get(pre-k);
            }
            map.put(pre, map.getOrDefault(pre,0)+1);
        }
        return count;
    
    }

    public int subarraySum2(int[] nums, int k) {
        //[1,2,2,3,4,4,4]
        //[1,3,5,8,12,16,20]
   		//res表示符合条件的子数组个数
        int res =0;
        //sum是前缀和数组
        int[] sum = new int[nums.length+1];
        //初始化sum[0]=0
        sum[0]=0;
        int m=1;
        //循环遍历数组得到前缀和数组
        for(int i=0;i<nums.length;i++){
            sum[m]=sum[m-1]+nums[i];
            m++;
        }
        //用双层循环去遍历所有子数组，在双层循环中，利用前缀和计算子数组和，如果子数组和=k，res+1;
        for(int i=0;i<sum.length-1;i++){
            for(int j=i+1;j<sum.length;j++){
                if(sum[j]-sum[i]==k){
                    res++;
                }
            }
        }
        
        return res;
    }
}
